package java学习.算法.动态规划.暴力递归与动态规划;

import java.util.HashMap;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/5/18 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 机器人运动问题 {

//    假设有排成一行的N个位置，记为1  ~ N,N一定大于等于2。
//    开始时机器人在其中的M位置上（M一定是1~N中的一个）。
//    如果机器人来到1位置，那么下一步只能往右来到2位置；
    //如果机器人来到N位置，那么下一步只能往左来到N-1的位置；

    //如果机器人来到中间位置，那么下一步可以往左走或者往右走；

    //规定机器人必须走K步，最终能来到P位置（P也是1~N中的一个）的方法有多少种？

    //给定四个参数N,M,K,P。返回方法数
    public static int robotWay(int N,int M,int K,int P){
        if (N<2||M<1||K<1 ||M>N||P>N||P<1){
//            排除无效条件
            return 0;
        }
        return  move(N,M,K,P);
    }

        /*
            N: 移动的范围，
            cur:当前位置，从M开始，到P（要求的结束位置）
            K：移动的次数
         */
        public static int move(int N,int cur,int K,int P){
        if (K==0){

            return cur==P? 1:0;
        }
        if (cur==1 ){ // N个位置，记为1  ~ N
            return move(N,2,K-1,P);
        }
        if (cur==N){
            return move(N,N-1,K-1,P);

        }
        return   move(N,cur+1,K-1,P) + move(N,cur-1,K-1,P);

    }


//    暴力递归存在重复计算，可以将重复的缓存，
//    将每次计算的缓存到数组中
//    cur的范围： 1~N  ，移动次数： 1~K

    public static int robotWayForCache(int N,int M,int K,int P){
        if (N<2||M<1||K<1 ||M>N||P>N||P<1){
//            排除无效条件
            return 0;
        }
        int [][]dp = new int[N+1][K+1];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= K; j++) {
                dp[i][j] = -1; // 没记录过的，记为-1.
            }
        }
        return  moveCache(N,M,K,P,dp);
    }

    /*
        N: 移动的范围，
        cur:当前位置，从M开始，到P（要求的结束位置）
        K：移动的次数
     */
    public static int moveCache(int N,int cur,int K,int P,int[][] dp){
        if (dp[cur][K]!=-1){ // 若不是-1，则已经记录过，直接返回缓存的值。
            return  dp[cur][K];
        }
        if (K==0){
            dp[cur][K] = cur==P? 1:0;
            return  dp[cur][K];
        }
        if (cur==1 ){ // N个位置，记为1  ~ N
            dp[cur][K] = moveCache(N,2,K-1,P,dp);
            return  dp[cur][K];
        }
        if (cur==N){
            dp[cur][K] = moveCache(N,N-1,K-1,P,dp);
            return  dp[cur][K];
        }
        dp[cur][K] =   moveCache(N,cur+1,K-1,P,dp) + moveCache(N,cur-1,K-1,P,dp);
        return  dp[cur][K];
    }

    public static void main(String[] args) {
        HashMap map=new HashMap(5);
        map.put("1","one");
        map.put("2","two");
        Object three = map.put("3", "three");
        Object four = map.put("3", "four");
        System.out.println(three);
        System.out.println(four);
        System.out.println(map.put("3", null));
        System.out.println(map.put("4", "nash"));
        System.out.println(map.put("4", "sh"));


    }


}
